package com.markus.code.图.图2;

import java.util.*;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/31 12:41
 * todo: 拓扑排序
 */
public class GraphTopologySort {
    public List<Node> topologySort(Graph graph){
        List<Node> ans = new ArrayList<>();
        if (graph == null){
            return ans;
        }
        //装载每个节点对应的入度的map结构
        HashMap<Node,Integer> inMap = new HashMap<>();
        //装载已经被遍历过的集合
        HashSet<Node> set = new HashSet<>();
        //将节点-入度存入map结构
        for (Map.Entry<Integer, Node> entry : graph.nodes.entrySet()) {
            Integer in = entry.getValue().in;
            inMap.put(entry.getValue(),in);
        }
        while(set.size() < inMap.size()){
            for (Map.Entry<Node, Integer> entry : inMap.entrySet()) {
                Node node = entry.getKey();
                if (!set.contains(node)){
                    if (entry.getValue() == 0){
                        set.add(node);
                        ans.add(node);
                        for (Node nextNode : node.nextNodes) {
                            inMap.put(nextNode,inMap.get(nextNode)-1);
                        }
                    }
                }
            }
        }
        return ans;
    }
}
